package demo.hw;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class _火车进站 {
    public static void main(String[] args) {
        /**
         * 给定一个正整数N代表火车数量，0<N<10,接下来输入火车入站的序列，一共N辆火车，每辆火车以数
         * 字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才
         * 能出站。
         * 要求输出所有火车出站的方案，以字典序排序Q输出。
         * 数据范围：1≤n≤10
         * 进阶：时间复杂度O(n!),空间复杂度：O(n)
         * 输入描述：
         * 第一行输入一个正整数N(0<N<=10),第二行包括N个正整数，范围为1到10。
         * 输出描述：
         * 输出以字典序从小到大排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见
         * sample。
         *
         * 示例1
         * 输入：
         * 3
         * 123
         * 输出：
         * 123
         * 132
         * 213
         * 231
         * 321
         * 说明：
         * 第一种方案：1进、1出、2进、2出、3进、3出
         * 第二种方案：1进、1出、2进、3进、3出、2出
         * 第三种方案：1进、2进、2出、1出、3进、3出
         * 第四种方案：1进、2进、2出、3进、3出、1出
         * 第五种方案：1进、2进、3进、3出、2出、1出
         * 请注意，[3,1,2]这个序列是不可能实现的。
         *
         * 核心思想：使用深度优先搜索（DFS）和回溯法模拟火车的进站和出站操作
         * 两个选择：
         *  ·让当前火车进站（如果还有未进站的火车）
         *  ·让站内火车出站（如果站内有火车）
         * 终止条件：所有火车都已处理且车站为空
         */

        int[] trains = {1, 2, 3};
        List<String> ret = new ArrayList<>();

        dfs(trains, 0, new Stack<>(), new StringBuilder(), ret);
        System.out.println(ret);
    }

    private static void dfs(int[] trains, int idx, Stack<Integer> s, StringBuilder out, List<String> ret) {
        // dfs:递归所有可能
        // idx:要进站火车的索引
        // out:记录当前出站顺序
        // s:模拟火车站
        if (idx == trains.length && s.isEmpty()) {
            ret.add(out.toString());
            return;
        }

        // 出站
        if (!s.isEmpty()) {
            int train = s.pop(); //栈中弹出火车
            out.append(train);// 记录出站顺序
            dfs(trains, idx, s, out, ret);//继续递归
            out.deleteCharAt(out.length() - 1);//回溯：删除刚才的记录
            s.push(train);// 回溯：把火车放入栈中
        }
        // 进站
        if (idx < trains.length) {
            s.push(trains[idx]);//火车进站
            dfs(trains, idx + 1, s, out, ret);//处理下一辆火车
            s.pop();//回溯：火车出站
        }
        /*
         * 初始状态：栈=[], out="", index=0
         *
         * 选择1：1进站 → 栈=[1], out="", index=1
         *    选择1.1：1出站 → 栈=[], out="1", index=1
         *       选择1.1.1：2进站 → 栈=[2], out="1", index=2
         *          选择1.1.1.1：2出站 → 栈=[], out="12", index=2
         *             选择1.1.1.1.1：3进站 → 栈=[3], out="12", index=3
         *                选择1.1.1.1.1.1：3出站 → 栈=[], out="123", index=3 ✅
         *    选择1.2：2进站 → 栈=[1,2], out="", index=2
         *       选择1.2.1：2出站 → 栈=[1], out="2", index=2
         *          选择1.2.1.1：3进站 → 栈=[1,3], out="2", index=3
         */
    }
}
